// Problem 200: Find the 200th prime-proof sqube containing the contiguous sub-string "200"

// We shall define a sqube to be a number of the form, p^2q^3, where p and q are distinct primes.
// For example, 200 = 5223 or 120072949 = 232613.
// The first five squbes are 72, 108, 200, 392, and 500.
// Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.
// Find the 200th prime-proof sqube containing the contiguous sub-string "200".
// ----
// Answer: 229161792008
// It is not difficult to find the squbes containing "200", but which are prime-proof?
// Since, it is allowed to change only one digit, for the numbers end with 2,4,5,6,8,0. If we don't change the last digit, the number must not be prime, therefore, replace the end number with 1,3,7,9. If all the number pass the test, the origin one must be prime-proof.
// While the number ends with 1,3,7,9, it is highly possible to change one digit to make it prime.

package main

import (
	"fmt"
	"math/big"
	"projecteuler/euler"
	"sort"
	"strings"
)

func p200() {
	euler.FillPrime(500_000)
	limit := big.NewInt(250000000000)
	var res []int
	for i, p := range euler.PrimeList {
		for _, q := range euler.PrimeList[i+1:] {
			var bp, bq, p2q3, p3q2 *big.Int
			bp = big.NewInt(int64(p))
			bq = big.NewInt(int64(q))
			p2q3 = big.NewInt(1)
			p3q2 = big.NewInt(1)
			p2q3.Exp(bp, big.NewInt(2), nil)
			p3q2.Exp(bq, big.NewInt(2), nil)
			bp.Exp(bp, big.NewInt(3), nil)
			bq.Exp(bq, big.NewInt(3), nil)
			p2q3.Mul(p2q3, bq)
			p3q2.Mul(p3q2, bp)
			if p3q2.Cmp(limit) == 1 {
				break
			}
			if strings.Contains(p2q3.String(), "200") && primeProof(p2q3) {
				res = append(res, int(p2q3.Int64()))
			}
			if strings.Contains(p3q2.String(), "200") && primeProof(p3q2) {
				res = append(res, int(p3q2.Int64()))
			}
		}
	}
	sort.Ints(res)
	fmt.Println("Problem 200:", res[199])
}

func primeProof(s *big.Int) bool {
	origin := s.Int64()
	if origin%2 == 0 || origin%10 == 5 {
		n := origin / 10 * 10
		d := [4]int64{1, 3, 7, 9}
		for _, v := range d {
			if euler.IsPrime(int(n + v)) {
				return false
			}
		}
	} else {
		return false
	}
	return true
}
